Search results for "Uncountable set"
showing 9 items of 9 documents
Uncountable Realtime Probabilistic Classes
2018
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.
Uncountable existentially closed groups in locally finite group classes
1990
In this paper, will always denote a local class of locally finite groups, which is closed with respect to subgroups, homomorphic images, extensions, and with respect to cartesian powers of finite -groups. Examples for x are the classes L ℐπ of all locally finite π-groups and L(ℐπ ∩ ) of all locally soluble π-groups (where π is a fixed set of primes). In [4], a wreath product construction was used in the study of existentially closed -groups (=e.c. -groups); the restrictive type of construction available in [4] permitted results for only countable groups. This drawback was then removed partially in [5] with the help of permutational products. Nevertheless, the techniques essentially only per…
Uncountable classical and quantum complexity classes
2018
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary la…
Polyhedrality and decomposition
2018
Abstract The aim of this note is to present two results that make the task of finding equivalent polyhedral norms on certain Banach spaces, having either a Schauder basis or an uncountable unconditional basis, easier and more transparent. The hypotheses of both results are based on decomposing the unit sphere of a Banach space into countably many pieces, such that each one satisfies certain properties. Some examples of spaces having equivalent polyhedral norms are given.
Quantum, stochastic, and pseudo stochastic languages with few states
2014
Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…
Upper bounds for the tightness of the $$G_\delta $$-topology
2021
We prove that if X is a regular space with no uncountable free sequences, then the tightness of its $$G_\delta $$ topology is at most the continuum and if X is, in addition, assumed to be Lindelof then its $$G_\delta $$ topology contains no free sequences of length larger then the continuum. We also show that, surprisingly, the higher cardinal generalization of our theorem does not hold, by constructing a regular space with no free sequences of length larger than $$\omega _1$$ , but whose $$G_\delta $$ topology can have arbitrarily large tightness.
Affine Surfaces With a Huge Group of Automorphisms
2013
We describe a family of rational affine surfaces S with huge groups of automorphisms in the following sense: the normal subgroup Aut(S)alg of Aut(S) generated by all algebraic subgroups of Aut(S) is not generated by any countable family of such subgroups, and the quotient Aut(S)/Aut(S)alg cointains a free group over an uncountable set of generators.
An uncountable family of almost nilpotent varieties of polynomial growth
2017
A non-nilpotent variety of algebras is almost nilpotent if any proper subvariety is nilpotent. Let the base field be of characteristic zero. It has been shown that for associative or Lie algebras only one such variety exists. Here we present infinite families of such varieties. More precisely we shall prove the existence of 1) a countable family of almost nilpotent varieties of at most linear growth and 2) an uncountable family of almost nilpotent varieties of at most quadratic growth.
Almost disjoint families of countable sets and separable complementation properties
2012
We study the separable complementation property (SCP) and its natural variations in Banach spaces of continuous functions over compacta $K_{\mathcal A}$ induced by almost disjoint families ${\mathcal A}$ of countable subsets of uncountable sets. For these spaces, we prove among others that $C(K_{\mathcal A})$ has the controlled variant of the separable complementation property if and only if $C(K_{\mathcal A})$ is Lindel\"of in the weak topology if and only if $K_{\mathcal A}$ is monolithic. We give an example of ${\mathcal A}$ for which $C(K_{\mathcal A})$ has the SCP, while $K_{\mathcal A}$ is not monolithic and an example of a space $C(K_{\mathcal A})$ with controlled and continuous SCP …